package com.apkcore.bl;

/**
 * https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/
 */
public class _圆圈中最后剩下的数字 {

    //

    /**
     * 数学公式可知递推公式
     * 设x = f(n-1,m);
     * 删除了第m%n个元素，将序列长度变为n-1,
     * 长度为n的序列最后一个删除元素=m%n开始的第x个元素
     * f(n,m) = (m%n+x)%n = (f(n-1,m)+m)%n
     */
    public int lastRemaining(int n, int m) {
        int x = 0;
        for (int i = 2; i <= n; i++) {
            x = (x+m)%i;
        }
        return x;
    }

}
